package algorithm;

/*
 * @author Jayarathina
 * @date May, 06, 2009 Website: http://www.madharasan.com/ This program performs
 * Kruskal's algorithm by Greedy programming technique.
 */

import java.io.*;

class Kruskal
{
    public static BufferedReader br = new BufferedReader(new InputStreamReader(
            System.in));
    
    static int[][] G;
    static int[][] t;
    static boolean[][] in;
    static boolean[][] temp;
    
    static int n;
    static int mincost = 0;
    static int k, l, num_ed = 0;
    
    public static void main(String[] args) throws IOException
    {
        System.out.println("\t\t\t\tPrim's Algorithm");
        System.out.print("\nEnter the number of the vertices: ");
        n = Integer.parseInt(br.readLine());
        
        G = new int[n + 1][n + 1];
        in = new boolean[n + 1][n + 1];
        t = new int[n + 1][3];
        
        System.out
                .print("\nIf edge between the following vertices enter its cost (not more than 7000) else 0:\n");
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                in[i][j] = in[j][i] = false;
                if ((i != j) && (i < j))
                {
                    System.out.print(i + " and " + j + ": ");
                    G[j][i] = G[i][j] = Integer.parseInt(br.readLine());
                    if (G[i][j] == 0)
                        G[j][i] = G[i][j] = 7001;
                }
                if (i == j)
                    G[i][j] = 7001;
            }
        
        System.out.println("\n\nSolution : \n\n");
        Kruskals();
        System.out.println("\n\n\n\ncost incured is: " + mincost);
    }
    
    static void Kruskals()
    {
        for (int i = 1; i <= n; i++)
        {
            getMinKL();
            if (k == l)
                break;
            System.out.print(l + "-" + k);
            if (formscycle(i - 1))
            {
                System.out.println(" --> Forms cycle, hence rejected!");
                i--;
                continue;
            }
            else
                System.out.println();
            
            mincost = mincost + G[k][l];
            num_ed = (isPresent(i, k)) ? num_ed : num_ed + 1;
            num_ed = (isPresent(i, l)) ? num_ed : num_ed + 1;
            
            t[i][1] = l;
            t[i][2] = k;
            if (num_ed >= n)
            {
                if (allconnect(i)) // not a forest
                    return;
            }
            
        }
        System.out.println("\nNo Solution Available!");
    }
    
    static boolean allconnect(int i)
    {
        for (int c = 2; c <= n; c++)
        {
            temp = new boolean[n + 1][n + 1];
            for (int a = 1; a <= n; a++)
                for (int b = 1; b <= n; b++)
                    temp[a][b] = temp[b][a] = false;
            
            if (can_reach(1, c, i) == false)
                return false;
        }
        return true;
    }
    
    static boolean formscycle(int i)
    {
        if (isPresent(i, k) && isPresent(i, l))
        {
            temp = new boolean[n + 1][n + 1];
            for (int a = 1; a <= n; a++)
                for (int b = 1; b <= n; b++)
                    temp[a][b] = temp[b][a] = false;
            
            if (can_reach(k, l, i))
                return true;
        }
        return false;
    }
    
    static boolean can_reach(int k, int l, int i)
    {
        temp[k][l] = temp[l][k] = true;
        for (int o = 1; o <= i; o++)
        {
            if (((k == t[o][1]) && (l == t[o][2]))
                    || ((l == t[o][1]) && (k == t[o][2])))
                return true;
            if ((k == t[o][1]) && !(temp[t[o][2]][l]))
            {
                if (can_reach(t[o][2], l, i) == true)
                    return true;
            }
            else
                if ((k == t[o][2]) && !(temp[t[o][1]][l]))
                {
                    if (can_reach(t[o][1], l, i) == true)
                        return true;
                }
        }
        return false;
    }
    
    static boolean isPresent(int i, int val)
    {
        for (int o = 1; o <= i; o++)
            if ((val == t[o][1]) || ((val == t[o][2])))
                return true;
        return false;
    }
    
    static void getMinKL()
    {
        int k1 = 1, l1 = 1;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                if ((i != j) && (i < j))
                {
                    if ((G[i][j] < G[k1][l1]) && G[i][j] != 0
                            && in[j][i] == false)
                    {
                        k1 = i;
                        l1 = j;
                    }
                }
            }
        if (G[k1][l1] != 0)
        {
            k = k1;
            l = l1;
            in[k][l] = in[l][k] = true;
        }
    }
}
